/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package open.algo.tree;

/**
 *
 * @author lee
 */
public class RedBlackTree
{

    class Node
    {

        int v = 0;
        boolean red = false;
        Node l = sentinel;
        Node r = sentinel;
        Node p = null;
    }
    Node sentinel = new Node();
    Node root = sentinel;

    public void insert(int v)
    {
        Node n = binaryInsert(v);
        n.red = true; //flag new node as red
        insertFixup(n);
    }

    private Node binaryInsert(int v)
    {
        Node p = root, c = root;
        while (c != sentinel)
        {
            p = c;
            if (c.v > v)
            {
                c = c.l;
            } else
            {
                c = c.r;
            }
        }

        Node n = new Node();
        n.v = v;
        n.p = p;
        if (p == sentinel)
        {
            root = n;
        } else
        {
            if (p.v > v)
            {
                p.l = n;
            } else
            {
                p.r = n;
            }
        }

        return n;
    }

    private void insertFixup(Node n)
    {
        while (n.p.red)
        {
            if (n.p.p.l == n.p)
            {
                Node uncle = n.p.p.r;
                if (uncle.red)
                {
                    n.p.red = false;
                    uncle.red = false;
                    n.p.p.red = true;
                    n = n.p.p;
                } else
                {
                    if (n.p.r == n)
                    {
                        n = n.p;
                        rotation_left(n);
                    }

                    n.p.red = false;
                    n.p.p.red = true;
                    rotation_right(n.p.p);
                }
            } else
            {
                //same with above, exchange left - right
                Node uncle = n.p.p.l;

                if (uncle.red)
                {
                    n.p.red = false;
                    uncle.red = false;
                    n.p.p.red = true;
                    n = n.p.p;
                } else
                {
                    if (n.p.l == n)
                    {
                        n = n.p;
                        rotation_right(n);
                    }

                    n.p.red = false;
                    n.p.p.red = true;
                    rotation_left(n.p.p);
                }
            }
        }

        root.red = false;
    }

    /**
     *       |
     *       x
     *     /   \
     *     *    y
     *         / \
     *         * *
     * @param n
     */
    private void rotation_left(Node n)
    {
        Node r = n.r; // not sentinel
        r.p = n.p;

        if (n.p == sentinel)
        {
            root = r;
        } else
        {
            if (n.p.l == n)
            {
                n.p.l = r;
            } else
            {
                n.p.r = r;
            }
        }

        n.r = r.l;
        if (r.l != sentinel)
        {
            r.l.p = n;
        }

        r.l = n;
        n.p = r;
    }

    /**
     *       |
     *       x
     *     /   \
     *     y    *
     *    / \
     *    * *
     *
     * @param n
     */
    private void rotation_right(Node n)
    {
        Node l = n.l; // not sentinel
        l.p = n.p;
        if (n.p == sentinel)
        {
            root = l;
        } else
        {
            if (n.p.l == n)
            {
                n.p.l = l;
            } else
            {
                n.p.r = l;
            }
        }

        n.l = l.r;
        if (l.r != sentinel)
        {
            l.r.p = n;
        }

        l.r = n;
        n.p = l;
    }

    public void print(Node n)
    {
        if (n == sentinel)
        {
            return;
        }

        System.out.println(n.v);
        print(n.l);
        print(n.r);
    }

    public static void main(String[] args)
    {
        RedBlackTree rbt = new RedBlackTree();
        for (int i = 0; i < 10; i++)
        {
            rbt.insert(i);
        }

        rbt.print(rbt.root);
    }
}
